﻿using System;

namespace Domain
{
    public class LeftSideHeap
    {
        public HeapItem item { get; private set; }
        public LeftSideHeap leftChild { get; private set; }
        public LeftSideHeap rightChild { get; private set; }
        public int rank { get; private set; }

        public LeftSideHeap()
        {
            item = null;
            leftChild = null;
            rightChild = null;
            rank = 0;
        }

        public bool isEmpty()
        {
            return (item == null);
        }

        public static int getRank(LeftSideHeap heap)
        {
            return heap == null ? 0 : heap.rank;
        }

        private void clear()
        {
            item = null;
            rank = 0;
            leftChild = null;
            rightChild = null;
        }

        private static LeftSideHeap clone(LeftSideHeap from)
        {
            if (from == null)
            {
                return null;
            }
            var to = new LeftSideHeap
                {
                    item = from.item,
                    rank = from.rank,
                    leftChild = clone(from.leftChild),
                    rightChild = clone(from.rightChild)
                };
            return to;
        }

        private static void copy(LeftSideHeap from, LeftSideHeap to)
        {
            to.item = from.item;
            to.rank = from.rank;
            to.leftChild = clone(from.leftChild);
            to.rightChild = clone(from.rightChild);
        }

        public static LeftSideHeap merge(LeftSideHeap heap1, LeftSideHeap heap2)
        {
            if (heap1 == null || heap1.isEmpty())
            {
                return heap2;
            }
            if (heap2 == null || heap2.isEmpty())
            {
                return heap1;
            }

            LeftSideHeap tmpHeap;
            if (heap1.item.key > heap2.item.key)
            {
                tmpHeap = heap1;
                heap1 = heap2;
                heap2 = tmpHeap;
            }
            var mergeHeap = new LeftSideHeap();
            copy(heap1, mergeHeap);
            tmpHeap = merge(heap1.rightChild, heap2);
            if (mergeHeap.rightChild == null)
            {
                mergeHeap.rightChild = new LeftSideHeap();
            }
            copy(tmpHeap, mergeHeap.rightChild);
 
            if (getRank(mergeHeap.leftChild) < getRank(mergeHeap.rightChild))
            {
                tmpHeap = mergeHeap.leftChild;
                mergeHeap.leftChild = mergeHeap.rightChild;
                mergeHeap.rightChild = tmpHeap;
            }

            mergeHeap.rank = Math.Min(getRank(mergeHeap.rightChild), getRank(mergeHeap.leftChild)) + 1;
            return mergeHeap;
        }

        public void insert(HeapItem newItem)
        {
            if (newItem == null)
            {
                throw new ArgumentNullException();
            }
            var newHeap = new LeftSideHeap {item = newItem, rank = 1};
            var mergeHeap = merge(this, newHeap);
            copy(mergeHeap, this);
        }

        public IHeapItemValue getMin()
        {
            return item == null ? null : item.value;
        }

        public IHeapItemValue deleteMin()
        {
            if (item == null)
            {
                return null;
            }

            var min = item.value;
            var mergeHeap = merge(leftChild, rightChild);
            if (mergeHeap == null)
            {
                clear();
            }
            else
            {
                copy(mergeHeap, this);
            }

            return min;
        }
    }
}
